package 剑指offer;

import java.util.Stack;

public class _54二叉搜索树的第k大节点 {
   public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
    int res, k;
    public int kthLargest1(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);
        if(k == 0) return;
        if(--k == 0) res = root.val;
        dfs(root.left);
    }

    public int kthLargest(TreeNode root, int k) {
        if(root == null || k <= 0){
            return 0;
        }

        Stack<TreeNode> st = new Stack<>();
        TreeNode node = root;
        do{
            while (node != null){
                st.push(node);
                node = node.right;
            }
            if(!st.isEmpty()){
                node = st.pop();
                k--;
                if(k == 0){
                    return node.val;
                }
                node = node.left;
            }
        }while (node != null || !st.isEmpty());
        return 0;
    }
}
